package com.agile.leetcode.hot.middle;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
 *
 * 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/recover-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author:ChenZhangKun
 * @Date: 2021/7/11 16:09
 */
public class RecoverTree {
    public static void main(String[] args) {
        // 创建数组
        List<Integer> list = new ArrayList<>();
        TreeNode tree = new TreeNode(1);
        // 中序遍历二叉树
        inOrderTranverse(tree, list);
        // 拿到交换的值
        int[] swappedNum = findSwappedNum(list);
        swapTree(tree,0, swappedNum);
    }

    private static void swapTree(TreeNode tree, int count, int[] swappedNum) {
        if (tree.val == swappedNum[0] || tree.val == swappedNum[1]) {
            tree.val = tree.val == swappedNum[0] ? swappedNum[0] : swappedNum[1];
            count++;
            if (count == 2) {
                return;
            }
        }
        if (tree.left != null) {
            swapTree(tree.left, count, swappedNum);
        }
        if (tree.right != null) {
            swapTree(tree.right, count, swappedNum);
        }
    }

    private static int[] findSwappedNum(List<Integer> nums) {
        int n = nums.size();
        int x = -1, y = -1;
        for (int i = 0; i < n - 1; ++i) {
            if (nums.get(i + 1) < nums.get(i)) {
                y = nums.get(i + 1);
                if (x == -1) {
                    x = nums.get(i);
                } else {
                    break;
                }
            }
        }
        return new int[]{x, y};
    }

    /**
     * 中序遍历
     * 因为中序遍历后在搜索二叉树中是有顺序的
     *
     * @param tree
     * @param list
     */
    private static void inOrderTranverse(TreeNode tree, List<Integer> list) {
        if (tree.left != null) {
            inOrderTranverse(tree.left, list);
        }
        list.add(tree.val);
        if (tree.right != null) {
            inOrderTranverse(tree.right, list);
        }
    }

}
